package com.zhengwl.study.sort;

import java.util.Arrays;

public class SwapSort implements Sort {

	private SortType sortType;

	public SwapSort() {
		sortType = SortType.BubbleSort;
	}
	public SwapSort(SortType type) {
		sortType = type;
	}

	// 冒泡排序
	@Override
	public void sort(int[] items) {
		if(sortType==SortType.QuickSort){
			quickSort(items);
		}else {
			bubbleSort(items);
		}
	}

	// 冒泡排序
	// 第1趟：依次比较0,1,2....n-1索引的元素，如果发现前一个数据大于后一个数据，交换它们。经过第一趟，最大的元素排到了最后
	// 第2趟：依次比较0,1,2....n-2索引的元素
	private void bubbleSort(int[] items) {
		/*
		for (int j = 0; j < items.length; j++) {
			for (int i = 0; i < items.length - j - 1; i++) {
				if (items[i] > items[i + 1]) {
					swap(items, i, i + 1);
				}
			}
		}
		*/

		for (int j = 0; j < items.length; j++) {
			// 是否发生交换标记
			boolean flag = false;
			for (int i = 0; i < items.length - j - 1; i++) {
				// 如果前一个元素大于后一个元素
				if (items[i] > items[i + 1]) {
					swap(items, i, i + 1);
					flag = true;
				}
			}
			// 如果某趟未发生交换，则说明已处于有序状态
			if (!flag) {
				break;
			}
		}
	}

	//快速排序：从待排序列中任取一个数据，作为分界值，所有比他小的元素放左边，比他大的元素放右边。这样一趟下来，该序列形成左右两个子序列，
	//接下来对左右两个子序列进行递归，对两个子序列重新选择中心元素并依此规则调整，直到每个子表元素只剩一个，排序完成。
	public void quickSort(int[] items) {
		subSort(items, 0,items.length-1);
		System.out.println("result:"+Arrays.toString(items));
	}

	private void subSort(int[] arr, int start, int end) {
		//需要排序
		if (start< end) {
			int tmp = arr[start];
			int i = start;
			int j = end;
			while (i < j) {
				while (i < j && arr[j] >= tmp) {
					j--;
				}
				while (i <j && arr[i] <= tmp) {
					i++;
				}
				
				if (i < j) {
					swap(arr,i,j);
				}
			}
			swap(arr, start, i);
			subSort(arr, start, i-1);
			subSort(arr, i+1, end);
		}
	}
}
